Integer relation algorithm

An integer relation between a set of real numbers x1, x2, ..., xn is a set of integers a1, a2, ..., an, not all 0, such that

a_1x_1 %2B a_2x_2 %2B \cdots %2B a_nx_n = 0.\,

An integer relation algorithm is an algorithm for finding integer relations. Specifically, given a set of real numbers known to a given precision, an integer relation algorithm will either find an integer relation between them, or will determine that no integer relation exists with coefficients whose magnitudes are less than a certain upper bound.[1]

Contents

History

For the case n = 2, an extension of the Euclidean algorithm can determine whether there is an integer relation between any two real numbers x1 and x2. The algorithm generates successive terms of the continued fraction expansion of x1/x2; if there is an integer relation between the numbers then their ratio is rational and the algorithm eventually terminates.

The first general algorithm that was proved to work for all values of n was the Ferguson–Forcade algorithm, published in 1979 by Helaman Ferguson and R.W. Forcade.[2] Subsequent developments, focussing on improving both efficiency and numerical stability, produced the following algorithms:

In 2000 the PSLQ algorithm was selected as one of the "Top Ten Algorithms of the Century" by Jack Dongarra and Francis Sullivan.[9]

Applications

Integer relation algorithms have two main applications. The first application is to determine whether a given real number x is likely to be algebraic, by searching for an integer relation between a set of powers of x {1, x, x2, ..., xn}. The second application is to search for an integer relation between a real number x and a set of mathematical constants such as e, π and ln(2), which will lead to an expression for x as a linear combination of these constants.

A typical approach in experimental mathematics is to use numerical methods and arbitrary precision arithmetic to find an approximate value for an infinite series, infinite product or an integral to a high degree of precision (usually at least 100 significant figures), and then use an integer relation algorithm to search for an integer relation between this value and a set of mathematical constants. If an integer relation is found, this suggests a possible closed-form expression for the original series, product or integral. This conjecture can then be validated by formal algebraic methods. The higher the precision to which the inputs to the algorithm are known, the greater the level of confidence that any integer relation that is found is not just a numerical artifact.

A notable success of this approach was the use of the PSLQ algorithm to find the integer relation that led to the Bailey-Borwein-Plouffe formula for the value of π. PSLQ has also helped find new identities involving multiple zeta functions and their appearance in quantum field theory; and in identifying bifurcation points of the logistic map. For example, where B4 is the logistic map's fourth bifurcation point, the constant α=-B4(B4-2) appears to be a root of a 120th-degree polynomial whose largest coefficient is 25730 or about 2·1072.[10] Integer relation algorithms are combined with tables of high precision mathematical constants and heuristic search methods in applications such as the Inverse Symbolic Calculator or Plouffe's Inverter.

The same applications can also be done with the LLL algorithm. Recent versions of LLL can handle problems with n above 500.

References

  1. ^ Since the set of real numbers can only be specified up to a finite precision, an algorithm that did not place limits on the size of its coefficients would always find an integer relation for sufficiently large coefficients. Results of interest occur when the size of the coefficients in an integer relation is small compared to the precision with which the real numbers are specified.
  2. ^ Weisstein, Eric W., "Integer Relation" from MathWorld.
  3. ^ Weisstein, Eric W., "LLL Algorithm" from MathWorld.
  4. ^ Weisstein, Eric W., "HJLS Algorithm" from MathWorld.
  5. ^ Johan Hastad, Bettina Just, Jeffrey Lagarias, Claus-Peter Schnorr: Polynomial time algorithms for finding integer relations among real numbers. Preliminary version: STACS 1986 (Symposium Theoret. Aspects Computer Science) Lecture Notes Computer Science 210 (1986), p. 105–118. SIAM J. Computing, Vol. 18 (1989), p. 859–881
  6. ^ Weisstein, Eric W., "PSOS Algorithm" from MathWorld.
  7. ^ Weisstein, Eric W., "PSLQ Algorithm" from MathWorld.
  8. ^ A Polynomial Time, Numerically Stable Integer Relation Algorithm by Helaman R. P. Ferguson and David H. Bailey; RNR Technical Report RNR-91-032; July 14, 1992
  9. ^ Barry A. Cipra. "The Best of the 20th Century: Editors Name Top 10 Algorithms". SIAM News 33 (4). http://amath.colorado.edu/resources/archive/topten.pdf. 
  10. ^ David H. Bailey and David J. Broadhurst, "Parallel Integer Relation Detection: Techniques and Applications," Mathematics of Computation, vol. 70, no. 236 (Oct 2000), pg. 1719-1736; LBNL-44481.

External links

Primality tests
Sieving algorithms
Integer factorization algorithms
Multiplication algorithms
Discrete logarithm algorithms
GCD algorithms
Modular square root algorithms
Other algorithms
Chakravala · Cornacchia · integer relation algorithm · integer square root · Modular exponentiation · Schoof's
Italics indicate that algorithm is for numbers of special forms; bold indicates deterministic algorithm for primality tests (current article is always in bold).